競プロ典型90問 010 Score Sum Queries
ちょっと問題を整理
code:in
7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
1
2 6
まず手元で計算
1番 1組 72
4番 1組 23
6番 1組 40
7番 1組 75
2番 2組 78
3番 2組 94
5番 2組 89
2 ~ 6番
1組について
1番, 4番, 6番, 7番のうち4番, 6番
23 + 40
2組について
2番, 3番, 5番のうち、2番, 3番, 5番
78 + 94 + 89
とやると、$ O(QN) ~ $ 10^{10}
とても間に合わない
クエリを渡って見てみると、毎回同じ足し合わせをしていることに気づく
しかも、区間の足し合わせをしている。
でも、どういう累積和を取る？
一組、二組ごとに累積和をとる
一組、二組に学籍番号何番の人がいるかを考えるのは面倒くさい
そういうのを無視して累積和をとって計算したい。
score_class1[i]: i番目未満のクラス1の学生の得点の累積和
score_class2[i]: i番目未満のクラス2の学生の得点の累積和
違うクラスにいる人は0点としてカウントすることで、累積和を取りやすくする。